package org.lintcode_Close.Stage1_Easy_50.O4字符串查找;

/**
 * @Auther: qingle
 * @Date: 2024/8/18-15:37
 * @Description: 对于一个给定的 source 字符串和一个 target 字符串，
 * 你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。
 * 如果不存在，则返回 -1。
 * KMP算法实现
 * @version: 1.0
 */
public class O4字符串查找KMP {

    public boolean KMP(String pattern, String text) {
        int N = text.length(), M = pattern.length();
        int[] lps = new int[M];
        computeLPSArray(pattern, M, lps);

        int i = 0, j = 0;
        while (i < N) {
            if (j == M) { // 完全匹配
                System.out.println("匹配位置：" + (i - j));
                j = lps[j - 1]; // 准备匹配下一个子串
            } else if (i < N && pattern.charAt(j) == text.charAt(i)) {
                i++; j++;
            } else {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
        return j == M; // 如果j等于M，表示最后一个字符匹配成功
    }

    public int KMPSearch(String source, String target) {
        // 处理空字符串的情况，直接返回0
        if (target.isEmpty()) {
            return 0;
        }
        // 如果源字符串或目标字符串为null，表示无法进行匹配，返回-1
        if (source == null || target == null) {
            return -1;
        }
        int N = source.length(), M = target.length();
        if (M == 0 || N == 0 || M > N) return -1; // 检查无效输入
        int[] lps = new int[M];
        computeLPSArray(target, M, lps); // 计算LPS数组

        int i = 0, j = 0, matchIndex = -1;
        while (i < N) {
            if (j == M) {
                matchIndex = i - M; // 记录匹配起始索引
                j = lps[j - 1]; // 准备匹配下一个子串
            } else if (i < N && (j == -1 || target.charAt(j) == source.charAt(i))) {
                i++;
                j++;
            } else {
                // j不为0且字符不匹配，根据LPS数组调整j
                j = (j != 0) ? lps[j - 1] : -1;
            }
        }
        return matchIndex;
    }


    void computeLPSArray(String pattern, int M, int[] lps) {
        lps[0] = 0;
        int j = 0;  // 表示当前匹配的长度
        for (int i = 1; i < M; ) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                lps[i++] = ++j;  // 匹配成功，i 和 j 都向前移动
            } else if (j != 0) {
                j = lps[j - 1];  // 匹配失败，但j不为0，根据之前的LPS值调整j
            } else {
                lps[i++] = 0;  // 匹配失败，且j为0，i向前移动
            }
        }
    }

    public static void main(String[] args) {
        O4字符串查找KMP test = new O4字符串查找KMP();
        System.out.println(test.KMPSearch("abcdefg", "def")); // 输出应为 3
        System.out.println(test.KMPSearch(null, "def")); // 输出应为 3
//        System.out.println(test.strStr("abcdefg", null)); // 输出应为 3
//        System.out.println(test.strStr(null, null)); // 输出应为 3
        System.out.println(test.KMPSearch("abcdefg", "")); // 输出应为 3
        System.out.println(test.KMPSearch("", "")); // 输出应为 3
    }
}
